GATE PYQ

Propositional Logic

Q31.
Suppose the predicate F(x,y,t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula \forall x \exists y \exists t(\neg F (x, y, t))?

Q32.
Which of the following is the negation of [\forall x, \alpha \rightarrow(\exists y, \beta \rightarrow(\forall u, \exists v, y))]

Q33.
Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: G(x): x is a gold ornament S(x): x is a silver ornament P(x): x is precious

Q34.
Consider the following well-formed formulae: I. \neg \forall x(P(x)) II. \neg \exists x(P(x)) III. \neg \exists x(\neg P(x)) IV. \exists x(\neg P(x)) Which of the above are equivalent?

Q35.
Which of the following first order formulae is logically valid? Here \alpha(x) is a first order formula with x as a free variable, and \beta is a first order formula with no free variable.

Q36.
Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that equivalent (a, b) means a and b are equivalent. Which of the following first order logic statements represents the following: Each finite state automaton has an equivalent pushdown automaton

Q37.
P and Q are two propositions. Which of the following logical expressions are equivalent? I. P\vee \sim Q II.\sim (\sim P \wedge Q) III.(P \wedge Q)\vee (P\wedge \sim Q)\vee (\sim P\wedge \sim Q) IV. (P\wedge Q)\vee \vee (P\wedge \sim Q)\vee (\sim P\wedge Q)

Q38.
Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: taller (x, y) is true if x is taller than y.

Q39.
Consider the following first order logic formula in which R is a binary relation symbol. \forall x \forall y(R(x, y) \Longrightarrow R(y, x)),The formula is

Q40.
Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x) be a predicate which denotes that x is connected. Which of the following first order logic sentences DOES NOT represent the statement: "Not every graph is connected"?